package 算法模板;

import java.util.Arrays;

/**
 * 冒泡排序：
 * 空间复杂度 O(1)、时间复杂度 O(n²)
 * 两两相邻的数字进行比较，如果符合条件则交换位置
 */
public class 冒泡排序 {

    public static void main(String[] args) {

        int[] nums = {2, 5, 2, 6, 3, 5, 343, 65, 2, 1, 0, -1};
        efficientBubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 当没有元素交换位置的时候退出循环
     *
     * @param nums
     */
    public static void bubbleSort(int[] nums) {
        boolean isChange = true;
        while (isChange) {
            isChange = false;
            //遍历到倒数第二个元素就行
            for (int i = 0; i < nums.length - 1; i++) {
                //从小到大排序
                if (nums[i] > nums[i + 1]) {
                    swaq(nums, i, i + 1);
                    isChange = true;
                }
            }
        }
    }

    /**
     * 优化：
     * 如果是升序排序，每一次冒泡，都会在尾部确定一个位置，不需要再进行比较
     *
     * @param nums
     */
    public static void efficientBubbleSort(int[] nums) {
        boolean isChange = true;
        //遍历到倒数第二个元素就行，每循环一次right--
        int right = nums.length - 1;
        while (isChange && right > 0) {
            isChange = false;
            for (int i = 0; i < right; i++) {
                //从小到大排序
                if (nums[i] > nums[i + 1]) {
                    swaq(nums, i, i + 1);
                    isChange = true;
                }
            }
            right--;
        }
    }


    public static void swaq(int[] nums, int a, int b) {
        //需要一个临时变量
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


}
